The present invention relates to a division and square root arithmetic unit including a divider of a higher radix type and a square root extractor of a lower radix type.
In mounting of a divider and a square root extractor, a device using a subtraction shift method or a subtraction separation method is generally employed as algorithm in consideration of the balance between a hardware amount and performance. This algorithm carries out a division by shifting a remainder or partial remainder and subtracting a multiple of a denominator (a divisor or a partially extracted square root) from the remainder to determine a quotient in a similar manner to a manual division calculation on paper. More specifically, a quotient or a number extracted from a square root is determined every n digits to calculate a partial remainder on the basis of the determined quotient or the extracted number from the square root. In the next operation step, the obtained partial remainder is shifted n digits to determine the next n-digit quotient or the square root extraction number on the basis of the n-digit shift of the partial remainder. Similarly, the operation is repeatedly performed.
This method for determining the quotient or square root extraction value every n digits is called, when the n-th power of 2 is defined to be equal to r (hereinafter referred to as radix), a division or square root extraction of radix r. A division and square root extraction processing of such algorithms has been described in Nonpatent Document 1 by Kai Hwang, “High Speed Arithmetic System of Computers”, 1980, Kindai Kagaku Sha Co., Ltd., pp. 214-249. This document has disclosed various division methods such as a restoring division, a nonrestoring division, an SRT (Sweeney, Robertson and Tocher) division and a generalized SRT division.
A procedure of a division using the subtraction shift method will be described briefly.
It is assumed that a bit length (a number of unit digits for determining a quotient or square root extraction number) of an operation is n (=arbitrary positive integer), a radix of the operation is r (=the n-th power of 2), a divisor is D, a dividend is R(0), a partial remainder at iteration j (j=a positive integer including 0) is R(j), and a quotient at iteration j is q(j). Furthermore, in this case, it is supposed that the divisor D and the dividend R(0) are normalized. In this instance, it is also assumed that as a normalized floating point format, “1. xxxx” is used, and both the divisor and the dividend are normalized. When a data form against this format is handled, a processing using this normalized floating point format can be applied by conducting a proper shift processing of data before and after an operation.
In this case, the quotient and the partial remainder are represented by redundant binary representations. That is, while each bit is expressed as {0 1} in twos complement representation, each bit is allowed to take three values {−1, 0, 1} and can be a negative value.
Under conditions that input data is normalized as described above, the quotient and the partial remainder can be consecutively determined by using the following recurrence equation (1).R(j+1)=r·R(j)−q(j+1)·D  (1)
In the SRT method, {−1} can be used as quotient digits besides {0, 1} and the quotient digits can be quickly determined by using several upper bits of the partial remainder. The SRT algorithm can be used for a square root extraction operation and hence division hardware can be utilized.
A procedure of a square root extraction operation will be descried briefly.
It is supposed that a radix of an operation is r, an extracted square root is R(0), a partial remainder at iteration j (j=a positive integer including 0) is R(j), a partially extracted square root is Q(j), and that a quotient at iteration j is q(j). It is also assumed that the extracted square root R(0) is normalized. The partially extracted square root Q(j) is the quotient calculated up to the j-th step.
In this instance, the used quotients (including the partially extracted square roots) and the partial remainders are represented by the redundant binary representation. That is, although each bit can be expressed as {0 1} in the twos complement representation, each bit is allowed to take three values {−1, 0, 1} and can be a negative value.
Under conditions that input data is normalized as described above, a quotient and a partial remainder can be successively obtained by using the following recurrence equations (2) and (3).R(j+1)=r·R(j)−q(j+1)·(r·Q(j)+q(j+1)·r−(j+1))  (2)Q(j+1)=Q(j)+q(j+1)·r−(j+1)  (3)
In the square root extraction operation, the algorithm is that a partial remainder at iteration j+1 is calculated by subtracting a partially extracted square root from a partial remainder at iteration j. The above operation is very complicated because the operation requires the partial remainder in the redundant binary representation and the partially extracted square root in the redundant binary representation. When, after all the partially extracted square roots in the redundant binary representation are obtained, the partially extracted square roots are converted into the twos complement representation, the time required for the conversion is added to the calculation time. This deteriorates processing performance.
Hence, in order to commonly use the hardware for the division, by using a circuit for an on-the-fly conversion, the partially extracted square root obtained simultaneously with the quotient is converted into the twos complement representation to carry out the operation with the partial remainder in the redundant binary representation and the partially extracted square root in the twos complement representation.
An on-the-fly conversion is disclosed in Nonpatent Document 2 by Milos D. Ercegovac and Tomas Lang, “On-the-fly Conversion of Redundant into Conventional Representations”, IEEE Transactions On Computers, Vol. C-36, No. 7, July 1987, pp. 895-897.
An on-the-fly conversion in the case of radix 2 will be described briefly.
For instance, a conversion of a redundant binary representation {1, −1} into the twos complement representation results in {1, 0} (both represent decimal number 1). If the redundant binary representation is converted into the twos complement representation using addition and subtraction, carry propagates when −1 is input. To present the carry propagation, in this case {0, 1} is previously prepared in addition to {1, 0} which is a value before −1 is input and {0, 1} is selected when −1 is input. That is, in order to execute the processing in a fixed time without causing the carry propagation, when a response (in other words, a representation smaller by 1) in the case where −1 is input is previously prepared, the carry propagation can be prevented.
Now, assuming that j decimal places of a quotient Q determined successively from the upper digit in the redundant binary representation and a quotient Z in the twos complement representation are Q(j) (=q(1)q(2) . . . q(j)) and Z(j) (=z(1)z(2) . . . z(j)) respectively, Z(j) can be represented from the above-description in a twos complement form of either Q(j) or Q(j)−2−j. Accordingly, when Q(j) and Q(j)−2−j in the twos complement form are held at each operation step, Z(j) can be immediately determined once q(j) is determined.
It is supposed that quotient digits at iteration j+1 during an operation is q(j+1), and that the twos complement forms of Q(j) and Q(j)−2−j are denoted as QP(j) and QN(j) respectively, which are referred to as a partial square root positive and a partial square root negative respectively. When the operation is executed according to the radix to determine q(j+1), from QP(j) and QN(j), QP(j+1) and QN(j+1) can be determined as follows:
                                          When            ⁢                                                                      ⁢                                                                    ⁢                          q              ⁡                              (                                  j                  +                  1                                )                                              =                                    -                        ⁢            1                          ,                              QP            ⁡                          (                              j                +                1                            )                                =                                                    QP                ⁡                                  (                  j                  )                                            -                              2                                  -                                      (                                          j                      +                      1                                        )                                                                        =                                                            QN                  ⁡                                      (                    j                    )                                                  +                                  2                                      -                    j                                                  -                                  2                                      -                                          (                                              j                        +                        1                                            )                                                                                  =                                                QN                  ⁡                                      (                    j                    )                                                  +                                                      2                                          -                                              (                                                  j                          +                          1                                                )                                                                              .                                                                                        (        4        )                                                      QN            ⁡                          (                              j                +                1                            )                                ⁢                      {                          =                                                QP                  ⁡                                      (                                          j                      +                      1                                        )                                                  -                                  2                                      -                                          (                                              j                        +                        1                                            )                                                                                            }                          =                                            QP              ⁡                              (                j                )                                      -                          2                              -                                  (                                      j                    +                    1                                    )                                                      -                          2                              -                                  (                                      j                    +                    1                                    )                                                              =                                                    QP                ⁡                                  (                  j                  )                                            -                              2                                  -                  j                                                      =                          QN              ⁡                              (                j                )                                                                        (        5        )                                                      When            ⁢                                                  ⁢                          q              ⁡                              (                                  j                  +                  1                                )                                              =          0                ⁢                                  ⁢                              QP            ⁡                          (                              j                +                1                            )                                =                      QP            ⁡                          (              j              )                                                          (        6        )                                          QN          ⁡                      (                          j              +              1                        )                          =                              QN            ⁡                          (              j              )                                +                      2                          -                              (                                  j                  +                  1                                )                                                                        (        7        )                                                      When            ⁢                                                  ⁢                          q              ⁡                              (                                  j                  +                  1                                )                                              =          1                ,                              QP            ⁡                          (                              j                +                1                            )                                =                                    QP              ⁡                              (                j                )                                      +                          2                              -                                  (                                      j                    +                    1                                    )                                                                                        (        8        )                                                      QN            ⁡                          (                              j                +                1                            )                                ⁢                      {                          =                                                QP                  ⁡                                      (                                          j                      +                      1                                        )                                                  -                                  2                                      -                                          (                                              j                        +                        1                                            )                                                                                            }                          =                                            QP              ⁡                              (                j                )                                      +                          2                              -                                  (                                      j                    +                    1                                    )                                                      -                          2                              -                                  (                                      j                    +                    1                                    )                                                              =                                    QP              ⁡                              (                j                )                                      .                                              (        9        )            
Equations (4), (7) and (8) can be expressed by the following equation:Qx(j+1)=Qy(j)+2−(j+1) assuming that a radix of the operation is 2.
It is sufficient for this operation to just connect a bit string of q(j+1) which is a quotient (0 or 1) of the (j+1)-th digit to the back of a partially extracted square root Qy(j) of up to the j-th digit. Therefore, no substantial operation is executed. It is sufficient for the other equations only to select either QP(j) or QN(j). That is because the partially extracted square root Q(j+1) at iteration j+1, namely QP(j+1), can be converted from a redundant binary form to a twos complement form (a normal number) through a simple bit operation where QP(j) as the partial square root positive at iteration j and QN(j) as the partial square root negative at iteration j are computed and stored.
Further, a division operation method according to the SRT method is disclosed in Japanese Patent Application Laid-Open No. 2001-222410, “Divider”(Patent Document 1). In this case, by scaling a divisor within a certain range such as 5/3≦divisor<1.75, upper 4 bits of a partial remainder is normalized and the normalized upper 4 bits are referred to, resulting in a determination of a quotient of 2 bits (a dividing circuit of a radix 4).
Since producing of a partial remainder in a division operation can be realized by a subtraction in consideration of a divisor D of a fixed value, a higher radix can be realized by scaling a range of a divisor. However, in producing a partial remainder in a square root extraction operation, a subtraction is carried out necessarily considering a partially extracted square root Q(j) at iteration j and a quotient q(j). In order to realize a higher radix, it is necessary to consider another quotient of a digit just ahead of the quotient generation unit. Hence, circuitry becomes complicated and the processing requires much time. A processing of a square root extraction operation of a higher radix is disclosed in Non-patent Document 3 by Milos D. Ercegovac and Tomas Lang, “Radix-4 Square root Without Initial PLA”, IEEE Transactions On Computers, Vol. 39, No. 8, August 1990, pp. 1016-1024. In this instance, a quotient of 2 bits can be determined on the basis of a partially extracted square root of 3 bits and the upper 7 bits of a partial remainder. However, when such a square root extraction operation for a higher radix is adopted, circuitry for determining a quotient is enlarged and complicated and a logic stage number is increased and complicated.
Further, a common use of a divider and a square root extractor has been proposed in Japanese Patent Application Laid-Open No. Hei 10-187420, “Divider and Square root Extractor”(Patent Document 2). This discloses a divider and a square root extractor according to a lower radix 2 and hence cannot execute a division of a higher radix and a square root extraction operation of a lower radix.
As described above, a square root extraction operation of a higher radix needs a complicated circuit having a larger number of logic stages than a division operation of a higher radix. When the same radix is adopted in a division operation and a square root extraction, processing performance depends on the number of logic stages in the square root extraction and processing performance of a division can deteriorate. In order to prevent the deterioration of the division processing performance, the radix of the square root extraction operation should be lower than that of the division operation. For example, to realize a circuit system for referring to upper 4 bits of a partial remainder in a square root extraction operation, radix 2 is preferred.